package q106
/**
LetCode q106 思路:
后序遍历的数组可以知道其最后的
 */

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
	//fmt.Printf("%v,%v\n",inorder,postorder)
	if len(inorder)==1{
		return &TreeNode{Val:inorder[0],Left:nil,Right:nil}
	}else if  len(inorder)<=0{
		return nil
	}

	headN:=postorder[len(postorder)-1]
	head:=&TreeNode{Val:headN}

	//查找
	findIndex:=0
	for i,n:=range inorder{
		if n==headN{
			findIndex=i
			break
		}
	}

	//fmt.Printf("headN: %d,findIndex:%d\n",headN,findIndex)

	leftLen:=len(inorder[:findIndex])
	rightLen:=len(inorder[findIndex+1:])
	head.Left=buildTree(inorder[:findIndex],postorder[:leftLen])
	head.Right=buildTree(inorder[findIndex+1:],postorder[leftLen:leftLen+rightLen])

	return head
}
